This disclosure relates generally to the field of computerized problem solving and in particular to a system and method for controlling multiple problem solving algorithms for continuous constraint satisfaction.
In certain control system applications, there exists a significant need for systems which can provide satisfactory decisions in critically time-constrained situations for complex systems having subsystems consisting of many networked sensors and actuators, with each subsystem having control, monitoring and fault diagnosis capabilities. Advances in hardware technology, such as inexpensive processors, low-cost micro-electromechanical systems (MEMS) actuators and sensors, and decreasing communication costs, result in systems with unprecedented reconfigurability, flexibility, and robustness. Such applications would benefit from the use of generic problem solvers, such as constraint solvers, to improve fault tolerance and reconfigurability. However, such problem solvers are typically not able to adapt their execution to or even execute within the resource bounds of the applications, such as time and memory limits.
However, most of these applications, such as control applications, pose problems that have exponential complexity, and a single constraint solving algorithm by itself is often not able to guarantee real-time performance and bounded memory use, or find the best result within a time bound, when faced with such problems.
Various forms of meta-heuristics have been proposed to combine global and local search heuristics, for both discrete and continuous optimization problems. For example, genetic algorithms for global search have been proposed using random local search, a conjugate gradient method, and stochastic approximation. GLO (Global Local Optimizer) software uses a genetic method as the global technique and variable metric nonlinear optimization as the local technique. LGO (Lipschitz-Continuous Global Optimizer) integrates several global (adaptive partition and random search based) and local (conjugate directions type) strategies as discussed in Pinter, J. D., “Global Optimization in Action”, Kluwer Academic Publishers, 1996. In Kitts, B., “Regulation of Complex Systems”, Proc. 1st Conference on Complex Systems, September 1997, Kitts presents an enumerative strategy (uniform random sampling) combined with a greedy strategy (hill-climbing). However, most of these approaches have been applied to unconstrained problems.
Similar work exists for combinatorial problems as well. For example, in Martin, O. C., “Combining Simulated Annealing with Local Search Heuristics”, G. Laporte and I. Osman, editors, Metaheuristics in Cominatorial Optimization, pages 57–75. Annual of Operations Research Vol. 63, 1996, a meta-heuristic called “Chained Local Optimization” embeds deterministic local search techniques into simulated annealing for traveling salesman and graph partitioning problems. Genetic algorithms have also been combined with local searches for combinatorial problems, as shown in Muhlenbein, Georges-Schleuter, and Kramer, “Evolution Algorithms in Combinatorial Optimization”, Parallel Computing, 7(65), 1988.
There is less work on cooperative solving of continuous constraint satisfaction problems (CSPs). Prior work by the inventors (“Method and System for Algorithm Synthesis in Problem Solving”, to Jackson et al., U.S. application Ser. No. 09/874,552, and “Adaptive Constraint Problem Solving Method and System”, to Fromherz et al., U.S. application Ser. No. 09/874,167) has been directed to cooperative solvers of various combinations of Adaptive Simulated Annealing, Nelder-Mead algorithm, Sequential Quadratic Programming, and the Interior-Point solving algorithm LOQO. However, none of these methods perform effort allocation for solvers systematically based on complexity analysis, nor do they explicitly take the time bound into account when selecting solvers and solver parameters. Also, none of them learn from on-line performance data to improve solver selection and transitioning between solvers. It would be useful to utilize adaptive strategies for transitioning between solvers for use with complex control applications.